package kmp;

import java.util.Arrays;

public class KMPAlgorithm {
    public static void main(String[] args) {
//        String s = "BBC ABCDAB ABCDABCDABDE";
//        String s1 = "ABCDABD";
        String s = "ABCD";
        String s1 = "BCD";
        System.out.println("s.length==="+s.length());
        System.out.println("s1.length==="+s1.length());
        int[] str =  kmpNext(s1);
        System.out.println(s);
        System.out.println(Arrays.toString(str));
        System.out.println( kmp(s,s1,str));
//        System.out.println(s.charAt(14));
//        System.out.println("21==========="+s.charAt(21));
//        System.out.println("7==========="+s.charAt(7));


    }

public static int kmp(String str,String kmp,int[] next){
for(int i =0,j=0;i<str.length();i++){


    while (j>0&&str.charAt(i)!=kmp.charAt(j)){
        j=next[j-1];
    }
    if(str.charAt(i)==kmp.charAt(j)){
        j++;
    }
    if(j==kmp.length()){
        System.out.println("kmp.length===="+kmp.length());
        return i-j;
    }
}
        return 0;
}
public static int kmpSearch(String str1, String str2, int[] next) {

    //����
    for(int i = 0, j = 0; i < str1.length(); i++) {

        //��Ҫ���� str1.charAt(i) ��= str2.charAt(j), ȥ����j�Ĵ�С
        //KMP�㷨���ĵ�, ������֤...
        while( j > 0 && str1.charAt(i) != str2.charAt(j)) {
            j = next[j-1];
        }

        if(str1.charAt(i) == str2.charAt(j)) {
            j++;
        }
        if(j == str2.length()) {//�ҵ��� // j = 3 i
            return i - j + 1;
        }
    }
    return  -1;
}
    public static int[] kmpNext(String str){
        System.out.println(str.length());
        int[] kmp = new int[str.length()];
        for(int i = 1, j = 0;i<kmp.length;i++){
            while (j>0&&str.charAt(i)!=str.charAt(j)){
//                j--;
                j=kmp[j-1];
            }
            if(str.charAt(i)==str.charAt(j)){
                j++;
            }
            kmp[i]= j;
        }
return kmp;
    }


}
